package com.Algorithm.DynamicProgramming.三角形问题;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zjz
 * @Date: 2022/04/11/13:55
 * @Description:
 * @Target:
 */
public class 跳台阶 {
    /*
    * 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

        数据范围：1≤n≤40
        要求：时间复杂度：O(n) ，空间复杂度： O(1)
        示例1
        输入：
        2
        返回值：
        2
        说明：
        青蛙要跳上两级台阶有两种跳法，分别是：先跳一级，再跳一级或者直接跳两级。因此答案为2
        示例2
        输入：
        7
        返回值：
        21

    *
    *
    * */

// 1 1
// 2 11 2
// 3 111 12 21
// 4 1111 121 211 112 22
// 5 11111 2111 1211 1121 1112  221 212 122
// 6 111111 21111 12111 11211 11121 11112
    //
    // 211 121 112
    //

    // 思路，不断锁定空箱子方法，由n变为(n+1)/2,箱子中每次减去一个1，本次的由上一次第一个开始变
    // 如5 11111
      /*
      * 5（11111）         11111
      * 4（1111）一个移动的1  2111 1211 1121 1112
      * 3（111） 两个移动的1  221 212
      * */


    public static int[] ints = new int[40];
    static int jumpFloor(int target) {
    if (ints[target]!=0){
        return ints[target];
    }
    if (target<=1){
        return 1;
    }else {
        return ints[target] =  jumpFloor(target-1)+jumpFloor(target-2);
    }

    }


    public static void main(String[] args) {
        System.out.println(jumpFloor(3));
    }
// 1 1 1
}
